package club.xiaojiawei.dp;

/**
 * @author 肖嘉威
 * @version 1.0
 * @date 6/2/22 10:23 PM
 * @question 416. 分割等和子集
 * @description 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
 */
public class CanPartition416 {

    public static void main(String[] args) {
        CanPartition416 test = new CanPartition416();
        boolean result = test.canPartition(new int[]{1, 5, 11, 5});
        System.out.println(result);
    }

    /**
     * 官方-dp（分组0/1背包）
     * @param nums
     * @return
     */
    public boolean canPartition(int[] nums) {
        int n = nums.length;
//        数量小于2,无法分为两个子数组
        if (n < 2) {
            return false;
        }
        int sum = 0, maxNum = 0;
        for (int num : nums) {
            sum += num;
            maxNum = Math.max(maxNum, num);
        }
//        和为奇数，无法分成两个相等的子数组
        if ((sum & 1) == 1) {
            return false;
        }
        int target = sum >> 1;
//        最大值大于和的一半，无法划分
        if (maxNum > target) {
            return false;
        }
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;
        for (int num : nums) {
            for (int j = target; j >= num; --j) {
                dp[j] |= dp[j - num];
            }
        }
        return dp[target];
    }
}
